//增减字符串匹配
class Solution {
public:
    vector<int> diStringMatch(string s) {
        //贪心：若遇到I则放入最小的那个数，若遇到D则放入当前最大的那个数
        int n = s.size();
        vector<int> ret(n+1);
        int left = 0 , right = n;
        for(size_t i = 0 ; i < n ; ++i)
        {
            if(s[i] == 'D') ret[i] = right--;
            else ret[i] = left++;
        }
        if(s[n-1] == 'I') ret[n] = right;
        else ret[n] = left;
        return ret;
    }
};

//分发饼干
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());

        int i = 0 , j = 0;
        while(j < s.size() && i < g.size())
        {
            if(s[j] >= g[i])
            {
                i++;
            }
            j++;
        }
        return i;
    }
};

//最优除法
class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return to_string(nums[0]);
        else if(n == 2) return to_string(nums[0])+'/'+to_string(nums[1]);

        string ret = to_string(nums[0]);
        ret += "/(";
        string temp;
        for(size_t i = 1 ; i < n ; ++i)
        {
            temp += to_string(nums[i]);
            temp += '/';
        }
        temp[temp.size() - 1] = ')';
        ret += temp;
        return ret;
    }
};

//跳跃游戏Ⅱ
class Solution {
public:
    int jump(vector<int>& nums) {
        int jumpCount = 0;
        int left = 0 , right = 0;
        int maxJump = 0 , n = nums.size();
        while(true)
        {
            while(left <= right)
            {
                if(left == n-1)
                {
                    return jumpCount;
                }
                maxJump = max(maxJump,nums[left]+left);
                left++; 
            }
            left = right + 1;
            right = maxJump;
            jumpCount++;
        }
        return 0;
    }
};

//跳跃游戏
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int left = 0 , right = 0;
        int maxJump = 0 , n = nums.size();
        while(true)
        {
            while(left <= right)
            {
                maxJump = max(maxJump,nums[left]+left);
                ++left;
            }
            left = right + 1;
            right = maxJump;
            if(left > right && left < n) return false;
            if(right >= n-1) return true;
        }
        return false;
    }
};

//加油站
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for(size_t i = 0 ; i < n ; )
        {
            int rest = 0;
            size_t step = 0;
            for(; step < n ; ++step)
            {
                size_t index = (i + step) % n;
                rest += (gas[index] - cost[index]);
                if(rest < 0) break; 
            }
            if(rest >= 0) return i;
            i += step+1;
        }
        return -1;
    }
};